package 队列.hard;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Lw中
 * @date 2021/7/17 22:59
 */
public class ErSanJiu {

    // 239. 滑动窗口最大值
    // 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。
    // 滑动窗口每次只向右移动一位。

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        // 创建数组存储仓库最大值
        int[] arr = new int[nums.length - k + 1];
        int index = 0;
        // 方法一：使用双端队列（单调队列）
        Deque<Integer> deque = new ArrayDeque<>();
        // 形成窗口
        for (int i = 0; i < k; i++) {
            // 保证窗口的最前边是最大值
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
        // 将对列头加入数组
        arr[index++] = deque.getFirst();
        // 移动窗口
        for (int i = k; i < nums.length; i++) {
            /**
             * LWZ TODO : 2021/7/18 if语句块的作用模糊不清
             */
            if(deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            arr[index++] = deque.peekFirst();
        }
        return arr;
    }

}
